/*
https://leetcode-cn.com/problems/largest-divisible-subset/solution/zui-da-zheng-chu-zi-ji-by-leetcode-solut-t4pz/
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution368 {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int[] f=new int[nums.length];
        Arrays.fill(f,1);
        int[] g=new int[nums.length];
        Arrays.fill(g,-1);
        for (int i=0;i<nums.length;i++){
            for (int j=0;j<i;j++){
                if (nums[i]%nums[j]==0 && f[j]+1>f[i]){
                    f[i]=f[j]+1;
                    g[i]=j;
                }
            }
        }
        List<Integer> l=new ArrayList<>();
        int max=-1,maxP=-1;
        for (int i=0;i<nums.length;i++){
            if (f[i]>max){
                max=f[i];
                maxP=i;
            }
        }
        do{
            l.add(0,nums[maxP]);
            maxP=g[maxP];
        }while(maxP!=-1);
        return l;
    }

    public static void main(String[] args) {
        System.out.println(new Solution368().largestDivisibleSubset(new int[]{1,2,3}));
    }
}
